package main

import (
	"fmt"
	"go-study/algorithm/common"
)

// 如何判断两个单链表（无环）是否交叉

func main() {
	head1 := &common.LNode{}
	common.CreateNode1(head1, 8)
	fmt.Println("head1：", head1)

	head2 := &common.LNode{}
	current2 := head2
	for i := 1; i < 5; i++ {
		current2.Next = &common.LNode{
			Data: i,
		}
		current2 = current2.Next
	}
	current2.Next = head1.Next.Next.Next.Next.Next
	fmt.Println("head2：", head2)

	interNode := isIntersect(head1, head2)
	fmt.Println("这两个链表相交点为：", interNode.Data)
}

// 方法一：Hash 法

// 方法二：首尾相接法 判断是否有环 参考 test6

// 方法三：尾结点法
func isIntersect(head1 *common.LNode, head2 *common.LNode) *common.LNode {
	if head1 == nil || head1.Next == nil || head1 == head2 ||
		head2 == nil || head2.Next == nil {
		return nil
	}

	current1 := head1.Next
	length1 := 0
	for current1.Next != nil {
		current1 = current1.Next
		length1++
	}

	current2 := head2.Next
	length2 := 0
	for current2.Next != nil {
		current2 = current2.Next
		length2++
	}

	if current1 != current2 {
		return nil
	}

	current1 = head1.Next
	current2 = head2.Next

	for length1 > length2 {
		current1 = current1.Next
		length1--
	}

	for length1 < length2 {
		current2 = current2.Next
		length2--
	}

	for current1 != current2 {
		current1 = current1.Next
		current2 = current2.Next
	}

	return current1
}
